package com.example.demo.leetcode.top100;

import java.util.LinkedList;
import java.util.List;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _62N皇后
 * @description
 * @date 2023/06/22 14:29
 * <p>
 * ******************************************************
 */
public class _62N皇后 {

    List<List<String>> result = new LinkedList<>();
    List<String> trace = new LinkedList<>();

    public List<List<String>> solveNQueens(int n) {
        List<String> board = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                sb.append('.');
            }
            board.add(sb.toString());
        }
        dfs(board, 0);
        return result;
    }

    private void dfs(List<String> board, int i) {

        if (i == board.size()) {
            result.add(new LinkedList<>(board));
            return;
        }

        for (int j = i; j < board.size(); j++) {
            if (!isValidQ(board, i, j)) {
                continue;
            }
            StringBuilder sb = new StringBuilder(board.get(i));
            sb.setCharAt(j, 'Q');
            board.set(i, sb.toString());
            dfs(board, i + 1);
            sb.setCharAt(j, '.');
            board.set(i, sb.toString());

        }


    }


    private boolean isValidQ(List<String> board, int row, int col) {

        // 检测同一列
        for (int k = 0; k < board.size(); k++) {
            if (board.get(k).charAt(col) == 'Q') {
                return false;
            }
        }

        // 检测左上方
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board.get(i).charAt(j) == 'Q') {
                return false;
            }
        }

        // 检测右上方
        for (int i = row - 1, j = col + 1; i >= 0 && j < board.size(); i--, j++) {
            if (board.get(i).charAt(j) == 'Q') {
                return false;
            }
        }

        return true;
    }
}
